package com.shawn.algorithm.back;

/**
 * 0-1背包问题
 */
public class ZeroOneBag {

	private int maxW = Integer.MIN_VALUE;
	/**
	 * 物品重量
	 */
	private int[] weight = {2, 2, 4, 6, 3};

	/**
	 * 物品数量
	 */
	private int n = 5;

	/**
	 * 背包最大承受重量
	 */
	private int w = 9;

	/**
	 * 备忘录，默认值false
	 */
	private boolean[][] mem = new boolean[5][10];

	/**
	 * @param i 考察到哪个物品
	 * @param cw 当前重量
	 * @param items 每个物品的重量
	 * @param n 物品的总数
	 * @param w 背包最大承受重量
	 */
	public void f(int i, int cw, int[] items, int n, int w) {
		// cw == w表示，当前重量已经是最大承受重量了
		// i == n表示所有物品都已经考察过
		if (cw == w || i == n) {
			if (cw > maxW) {
				maxW = cw;
			}
			System.out.println("i = " + i + "\t, cw = " + cw + "\t, maxW = " + maxW);
			return;
		}
		// 重复状态
		if (mem[i][cw]) {
			return;
		}
		mem[i][cw] = true;
		// 选择不装第i个物品
		f(i + 1, cw, items, n, w);
		if (cw + items[i] <= w) {
			// 选择装第i个物品
			f(i + 1, cw + items[i], items, n, w);
		}
	}

	public static void main(String[] args) {
		ZeroOneBag bag = new ZeroOneBag();
		bag.f(0, 0, bag.weight, bag.n, bag.w);
	}

}
